#include <iostream>

/*
子集背包问题
*/

bool backpack(int nums[], int N)
{
    //选择：是否把nums[i]装进背包
    int sum = 0;
    for (int i = 0; i < N; i++)
        sum += nums[i];
    if (sum % 2 != 0)
        return false;
    int W = sum / 2; //背包容量
    bool dp[N+1][W+1];
    
    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= W; j++)
            dp[i][j] = false;

    //如何判断是否将nums[i]加入背包；
    // dp[i][j]对于前i个数字，在背包容量j的限制下是否能装满
    // 如果没有把nums[i]加入j的背包，
    // 注意：这里的dp[i][j]表示对前i个数字选择加入背包，并不是前i个全部加入。
    /*
    dp[0][j] = false //表示没有物品，
    dp[i][0] = false //表示没有容量

    如果nums[i]物品加入，
    如果dp[i-1][j] == true,那么就没有容量了
    if (dp[i-1][j] == true)
        dp[i][j] == false
    if (dp[i-1][j] == false)
        [11, ..]
        if (j - nums[i] <= 0) 当前总容量不够
            false
        if dp[i-1][j - nums[i]] = true
            dp[i][j] = true
        if dp[i-1][j - nums[i]] = false
            dp[i][j] = false
    如果nums[i]物品不加入
    if (dp[i-1][j] == true) dp[i][j] == true
    else dp[i][j] = false
    */
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if (dp[i-1][j] == true)
            {
                //再加入就是false了，如果不加入还是true，所以选择不加入
                dp[i][j] = true;
            }
            else
            {
                bool add_res = true;
                //如果不加入，结果肯定是false，只看加入的结果了
                if (j - nums[i-1] < 0)
                    add_res = false;
                else if (j - nums[i-1] == 0)
                    add_res = true;
                else if (dp[i-1][j - nums[i-1]] == false)
                    add_res = false;
                dp[i][j] = add_res;
            }
        }
    }
    for (int i = 0; i <= N; i++)
    {    for (int j = 0; j <= W; j++)
        {
            std::cout << dp[i][j] << " ";
        }
        std::cout << "\n";
    }
    return dp[N][W];
}
int main()
{
    using namespace std;
    int nums[4] = {1, 2, 3, 5};
    cout << backpack(nums, 4) << endl; 

    return 0;
}